import java.util.*;

public class Merge {
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {
        // write code here
        ArrayList<Interval> ret = new ArrayList<>();
        if (intervals.size() == 0) {
            return ret;
        }
        Collections.sort(intervals, (a,b) -> {
            return a.start == b.start ? a.end-b.end : a.start-b.start;
        });
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); i++) {
            Interval curInterval = intervals.get(i);
            if (end < curInterval.start) {
                Interval interval = new Interval(start, end);
                ret.add((interval));
                start = curInterval.start;
                end = curInterval.end;
            } else {
                if (end < curInterval.end) {
                    end = curInterval.end;
                }
            }
        }
        Interval lastInterval = new Interval(start, end);
        ret.add(lastInterval);
        return ret;
    }
}
